#include <vector>
#include <cstddef>

using std::vector;

namespace Sort
{
    /**
     * @brief 插入排序
     *
     * @tparam T
     * @param vec       排序数组
     * @param order     True则由小到大 否则由大到小
     * @return vector<T>
     */
    template <typename T>
    vector<T> insertionSort(const vector<T> &vec, bool order = true)
    {
        vector<T> ret(vec.size());
        ret[0] = vec[0];
        // 逐元素比较
        for (int i = 1; i < vec.size(); i++)
        {
            int j = 0;
            for (; j < i; j++)
            {
                // 插入
                if (vec[i] > ret[j] ^ order)
                {
                    // 后移
                    int k = i;
                    while (k != j)
                    {
                        ret[k] = ret[k - 1];
                        k--;
                    }
                    // 插入
                    ret[j] = vec[i];
                    break;
                }
            }
            // 未插入
            if (j == i)
                ret[i] = vec[i];
        }
        return ret;
    }

    template <typename T>
    vector<T> merge(const vector<T> &vec, size_t pbegin, size_t pend, bool order = true)
    {
        vector<T> ret;
        if (pend == pbegin + 1)
        {
            ret.push_back(vec[pbegin]);
            return ret;
        }

        size_t pos = pbegin + (pend - pbegin) / 2;
        auto v1 = merge(vec, pbegin, pos, order);
        auto v2 = merge(vec, pos, pend, order);

        size_t len1 = v1.size();
        size_t len2 = v2.size();
        int p1 = 0;
        int p2 = 0;

        while (1)
        {
            if (p1 >= len1)
            {
                ret.insert(ret.end(), v2.begin() + p2, v2.end());
                break;
            }
            else if (p2 >= len2)
            {
                ret.insert(ret.end(), v1.begin() + p1, v1.end());
                break;
            }

            if (v1[p1] > v2[p2] ^ order)
                ret.push_back(v1[p1++]);
            else
                ret.push_back(v2[p2++]);
        }
        return ret;
    }

};